/*
 *  3-way quick sort
 */
package algs4.sort;

public class Quick3way
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int st, int ed) {
        // base case
        if (ed <= st) return;

        int lt = st;
        int gt = ed;
        int i  = st + 1;

        Comparable v = a[st];

        while (i <= gt) {
            int cmp = a[i].compareTo(v);

            if      (cmp < 0) exch(a, i++, lt++);
            else if (cmp > 0) exch(a, i, gt--);
            else              i++;
        }

        sort(a, st, lt - 1);
        sort(a, gt + 1, ed);
    }

    private static void exch(Object[] a, int p, int q) {
        Object v = a[p];

        a[p] = a[q];
        a[q] = v;
    }
}
